#ifndef __UTF8CODE_H__
#define __UTF8CODE_H__

/*
  该头文件包含UTF-8编码的各种操作，且被反复使用
  不妨将其命名为UTF8Code.hpp
  里面仅包含全局函数
 */
#include <string>
using std::string;
using std::size_t;

static size_t nBytesCode(const char ch) {
	if (ch & (1 << 7)) {
		int nBytes = 1;
		for (int idx = 0; idx != 6; ++idx) {
			if (ch & (1 << (6 - idx))) {
				++nBytes;
			} else
				break;
		}
		return nBytes;
	}
	return 1;
}

//计算实际的有效字符数，例如字符串“中国”，有效字符个数为2，而实际长度为6（UTF-8编码）
 static std::size_t length(const std::string &str) {
	std::size_t ilen = 0;
	for (std::size_t idx = 0; idx != str.size(); ++idx) {
		int nBytes = nBytesCode(str[idx]);
		//为何是idx += (nBytes - 1)  因为for循环的还要执行一次++idx
		idx += (nBytes - 1);
		++ilen;
	}
	return ilen;
}

 static int triple_min(const int &a, const int &b, const int &c) {
	return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

 static int editDistance(const std::string & lhs, const std::string &rhs) {
	//计算最小编辑距离-包括处理中英文
	size_t lhs_len = length(lhs);
	size_t rhs_len = length(rhs);
	int editDist[lhs_len + 1][rhs_len + 1];
	for (size_t idx = 0; idx <= lhs_len; ++idx) {	//初始化列
		editDist[idx][0] = idx;
	}

	for (size_t idx = 0; idx <= rhs_len; ++idx) {	//初始化行
		editDist[0][idx] = idx;
	}

	std::string sublhs, subrhs;
	for (std::size_t dist_i = 1, lhs_idx = 0; dist_i <= lhs_len; ++dist_i, ++lhs_idx) {
		size_t nBytes = nBytesCode(lhs[lhs_idx]);
		sublhs = lhs.substr(lhs_idx, nBytes);
		lhs_idx += (nBytes - 1);

		for (std::size_t dist_j = 1, rhs_idx = 0; dist_j <= rhs_len; ++dist_j, ++rhs_idx) {
			nBytes = nBytesCode(rhs[rhs_idx]);
			subrhs = rhs.substr(rhs_idx, nBytes);
			rhs_idx += (nBytes - 1);
			if (sublhs == subrhs) {
				editDist[dist_i][dist_j] = editDist[dist_i - 1][dist_j - 1];
			} else {
				editDist[dist_i][dist_j] = triple_min(
				                               editDist[dist_i][dist_j - 1] + 1,
				                               editDist[dist_i - 1][dist_j] + 1,
				                               editDist[dist_i - 1][dist_j - 1] + 1);
			}
		}
	}
	return editDist[lhs_len][rhs_len];
}

#endif
